/**
 * 螺旋矩阵
 *
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 *
 * 示例 1：
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 *
 * 示例 2：
 * 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
 * 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
 *
 * 提示：
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 10
 * -100 <= matrix[i][j] <= 100
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 直接模拟, 我们就是从最外层开始遍历, 像剥洋葱一样, 一层一层的将这题剥开
 * 我们设置一个变量来记录剥的层数, 这个要使用 m n 中最小的来筛选, 后面就是
 * 最外层的遍历, 我们从 右, 下, 左, 上, 来遍历, 这里有个细节咱要处理, 就是
 * 要是要剥的只有一层的话, 咱已经遍历完一遍, 后面要是在遍历一遍的话, 肯定会重复
 * 遍历, 所以我们在后面一层 左, 上的遍历中, 要加上判断, 是否重合了, 要是重合了
 * 就 return
 * 时间复杂度 : O(m * n)
 * 空间复杂度 : O(m * n)
 */

public class Main {

    // 定义全局变量
    List<Integer> list;
    int m, n, tmp;
    int[][] nums;

    public List<Integer> spiralOrder(int[][] matrix) {

        // 初始化
        list = new ArrayList<>();
        m = matrix.length;
        n = matrix[0].length;
        nums = matrix;

        // 这里求 m n 的较小一个
        tmp = Math.min(m, n);

        // 这里也要注意, 要是偶数的话, 直接除2 就是层数, 要是奇数的话,
        // 因为少了 1, 所以我们要加上 1
        tmp = tmp % 2 == 0 ? tmp / 2 : tmp / 2 + 1;

        // 循环处理层数
        for (int i = 0; i < tmp; i++) {
            dfs(i);
        }

        return list;
    }

    private void dfs (int k) {

        // 右
        for (int i = k; i < n - k; i++) {
            list.add(nums[k][i]);
        }

        // 下
        for (int i = k + 1; i < m - k; i++) {
            list.add(nums[i][n - k - 1]);
        }

        // 这里要是和上面重合, 就要 return
        if (m - k - 1 == k || k == n - k - 1) {
            return;
        }

        // 左
        for (int i = n - k - 1 - 1; i >= k; i--) {
            list.add(nums[m - k - 1][i]);
        }

        // 上
        for (int i = m - k - 1 - 1; i > k; i--) {
            list.add(nums[i][k]);
        }
    }

    public static void main(String[] args) {
        Main test = new Main();
//        int[][] arr = new int[][]{
//                {1, 2, 3},
//                {4, 5, 6},
//                {7, 8, 9}
//        };
        int[][] arr = new int[][]{
                { 2, 5, 8},
                {-1, 0, 4}
        };
        test.spiralOrder(arr);
    }
}